{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path Sum IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #array #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #数组 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #路径总和 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>对于一棵深度小于&nbsp;<code>5</code>&nbsp;的树，可以用一组三位十进制整数来表示。对于每个整数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>百位上的数字表示这个节点的深度 <code>d</code>，<code>1 &lt;= d&nbsp;&lt;= 4</code>。</li>\n",
    "\t<li>十位上的数字表示这个节点在当前层所在的位置 <code>P</code>， <code>1 &lt;= p&nbsp;&lt;= 8</code>。位置编号与一棵满二叉树的位置编号相同。</li>\n",
    "\t<li>个位上的数字表示这个节点的权值 <code>v</code>，<code>0 &lt;= v&nbsp;&lt;= 9</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个包含三位整数的&nbsp;<strong>升序&nbsp;</strong>数组&nbsp;<code>nums</code>&nbsp;，表示一棵深度小于 <code>5</code> 的二叉树，请你返回 <em>从根到所有叶子结点的路径之和&nbsp;</em>。</p>\n",
    "\n",
    "<p><strong>保证&nbsp;</strong>给定的数组表示一个有效的连接二叉树。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/30/pathsum4-1-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [113, 215, 221]\n",
    "<strong>输出:</strong> 12\n",
    "<strong>解释:</strong> 列表所表示的树如上所示。\n",
    "路径和 = (3 + 5) + (3 + 1) = 12.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/30/pathsum4-2-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [113, 221]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> 列表所表示的树如上所示。\n",
    "路径和 = (3 + 1) = 4.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 15</code></li>\n",
    "\t<li><code>110 &lt;= nums[i] &lt;= 489</code></li>\n",
    "\t<li><code>nums</code>&nbsp;表示深度小于&nbsp;<code>5</code> 的有效二叉树</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-sum-iv](https://leetcode.cn/problems/path-sum-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-sum-iv](https://leetcode.cn/problems/path-sum-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[113,215,221]', '[113,221]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.nodes = {}\n",
    "        for num in nums:\n",
    "            code = num // 10\n",
    "            val = num % 10\n",
    "            self.nodes[code] = val\n",
    "\n",
    "        root = nums[0] // 10\n",
    "\n",
    "        self.res = 0\n",
    "        self.traverse(root, 0)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root, path):\n",
    "        if root not in self.nodes:\n",
    "            return \n",
    "\n",
    "        path += self.nodes[root]\n",
    "\n",
    "        row, col = self.decode(root)\n",
    "        left = (row + 1) * 10 + (2 * col - 1)\n",
    "        right = (row + 1) * 10 + (2 * col)\n",
    "\n",
    "        if left not in self.nodes and right not in self.nodes:\n",
    "            self.res += path\n",
    "\n",
    "        self.traverse(left, path)\n",
    "        self.traverse(right, path)\n",
    "\n",
    "    def decode(self, code):\n",
    "        row = code // 10\n",
    "        col = code % 10\n",
    "        return row, col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = [[None] * (2**i) for i in range(4)]\n",
    "        total = 0\n",
    "\n",
    "        for num in nums:\n",
    "            d = (num//100) - 1\n",
    "            p = ((num//10) % 10) - 1\n",
    "            v = num % 10\n",
    "\n",
    "            tree[d][p] = [v, True]\n",
    "        \n",
    "        for d in range(3, -1, -1):\n",
    "            for p, node in enumerate(tree[d]):\n",
    "                if not node or not node[1]:\n",
    "                    continue\n",
    "                \n",
    "                s = 0\n",
    "                d_ = d\n",
    "                p_ = p\n",
    "                while d_ >= 0:\n",
    "                    s += tree[d_][p_][0]\n",
    "                    tree[d_][p_][1] = False\n",
    "                    d_ -= 1\n",
    "                    p_ //= 2\n",
    "                \n",
    "                total += s\n",
    "        \n",
    "        return total\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        cnt = Counter()\n",
    "        for num in nums:\n",
    "            d, p, v = num // 100, num // 10 % 10, num % 10\n",
    "            fa = (d - 1, (p + 1) // 2)\n",
    "            cnt[(d, p)] += cnt[fa] + v\n",
    "        res = 0\n",
    "        for (d, p), v in cnt.items():\n",
    "            if (d + 1, p * 2 - 1) not in cnt and (d + 1, p * 2) not in cnt:\n",
    "                res += v\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        # print(1//2) # 0\n",
    "        rootToPath = dict() # 从key到root的path sum, root为1\n",
    "        rootToPath[0] = 0\n",
    "        for num in nums:\n",
    "            depth = num // 100\n",
    "            pos = num // 10 % 10\n",
    "            val = num % 10\n",
    "            idx = 2**(depth - 1) + pos - 1\n",
    "            rootToPath[idx] = rootToPath[idx//2] + val\n",
    "        res = 0\n",
    "        for path, val in rootToPath.items():\n",
    "            if not path * 2 in rootToPath and not path * 2 + 1 in rootToPath:\n",
    "            # if leaf node\n",
    "                res += val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        H = nums[-1] // 100\n",
    "        lst = [0] * (2**H)\n",
    "        i = len(nums) - 1\n",
    "        res = 0\n",
    "        for l in range(H, 0, -1):\n",
    "            new_lst = []\n",
    "            for j in range(2 ** (l - 1)):\n",
    "                new_lst.append(lst[2 * j] + lst[2 * j + 1])\n",
    "\n",
    "            while i >= 0 and nums[i] // 100 >= l:\n",
    "                v = nums[i] % 10\n",
    "                p = (nums[i] // 10) % 10\n",
    "                if new_lst[p-1] == 0:\n",
    "                    new_lst[p-1] = 1\n",
    "                res += v * new_lst[p-1]\n",
    "                i -= 1\n",
    "\n",
    "            lst = new_lst\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = defaultdict(list)\n",
    "\n",
    "        for node in nums:\n",
    "            level = node // 100\n",
    "            position = (node - (level * 100)) // 10\n",
    "            value = node % 10\n",
    "            tree[level*10 + position].append(value)\n",
    "            parent_level = level - 1\n",
    "            parent_position = (position + 1) // 2\n",
    "            if (parent_level * 10 + parent_position) in tree:\n",
    "                tree[(parent_level * 10 + parent_position) ].append(level*10 + position)\n",
    "\n",
    "        print(tree)\n",
    "        path = []\n",
    "        self.dfs(11, tree, 0, path)\n",
    "        add_up = 0 \n",
    "        for i in path:\n",
    "            add_up += i\n",
    "        return add_up\n",
    "\n",
    "    def dfs(self, node, tree, cur_sum, path):\n",
    "        if len(tree[node]) < 2: # leave node\n",
    "            cur_sum += tree[node][0]\n",
    "            path.append(cur_sum)\n",
    "            return \n",
    "\n",
    "        cur_sum += tree[node][0] # add current node value to the sum value\n",
    "        self.dfs(tree[node][1], tree, cur_sum, path)\n",
    "        if len(tree[node]) > 2:\n",
    "            self.dfs(tree[node][2], tree, cur_sum, path)\n",
    "        return\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        dic = defaultdict(int) # key (row, col) -> val\n",
    "        for num in nums:\n",
    "            h = num // 100\n",
    "            d = (num//10) % 10\n",
    "            dic[(h, d)] += dic[(h-1, (d+1)//2)] + num % 10  # 113 % 10 = 3\n",
    "        res = 0\n",
    "        for (h, d), v in dic.items():\n",
    "            if (h+1, 2*d-1) not in dic and (h+1, 2*d) not in dic:\n",
    "                res += v\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#       11\n",
    "#    21    22\n",
    "#   31 32 33 34\n",
    "\n",
    "#    d \n",
    "#    2*(d-1) + 1 = 2d-1\n",
    "#    2*(d-1) + 2 = 2d\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        cnt=Counter()\n",
    "        for num in nums:\n",
    "            d,p,v=num//100,(num//10)%10,num%10\n",
    "            fa=(d-1,(p+1)//2)\n",
    "            cnt[(d,p)]+=cnt[fa]+v\n",
    "\n",
    "        res=0\n",
    "        for (d,p),v in cnt.items():\n",
    "            if (d+1,p*2-1) not in cnt and (d+1,p*2) not in cnt:\n",
    "                res+=v\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        l = [-1] * 31\n",
    "        for n in nums:\n",
    "            d = n // 100\n",
    "            p = (n // 10) % 10\n",
    "            v = n % 10\n",
    "            i = 2 ** (d - 1) - 1 + p - 1\n",
    "            l[i] = v\n",
    "\n",
    "        self.ret = 0\n",
    "        def dfs(i, s, l):\n",
    "            s += l[i]\n",
    "            lc = 2 * i + 1\n",
    "            rc = 2 * i + 2\n",
    "            bl = l[lc] > -1\n",
    "            br = l[rc] > -1\n",
    "            if not bl and not br:\n",
    "                self.ret += s\n",
    "                return\n",
    "            if bl:\n",
    "                dfs(lc, s, l)\n",
    "            if br:\n",
    "                dfs(rc, s, l)\n",
    "        dfs(0, 0, l)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        value = {(1,1): int(nums[0]%10)}\n",
    "        for num in nums:\n",
    "            if int(num / 100) > 1:\n",
    "                str_num = str(num)\n",
    "                f, s, v = int(str_num[0]), int(str_num[1]), int(str_num[2])\n",
    "                father = (f-1, int((s+1)/2))\n",
    "                value[(f,s)] = value[father] + v\n",
    "        res = 0\n",
    "        for (f,s) ,v in value.items():\n",
    "            if (f+1 , s*2-1) not in value and (f+1, s*2) not in value:\n",
    "                res += v\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = defaultdict(list)\n",
    "\n",
    "        for node in nums:\n",
    "            level = node // 100\n",
    "            position = (node - (level * 100)) // 10\n",
    "            value = node % 10\n",
    "            tree[level*10 + position].append(value)\n",
    "            parent_level = level - 1\n",
    "            parent_position = (position + 1) // 2\n",
    "            if (parent_level * 10 + parent_position) in tree:\n",
    "                tree[(parent_level * 10 + parent_position) ].append(level*10 + position)\n",
    "        path = []\n",
    "        self.dfs(11, tree, 0, path)\n",
    "        add_up = 0 \n",
    "        for i in path:\n",
    "            add_up += i\n",
    "        return add_up\n",
    "\n",
    "    def dfs(self, node, tree, cur_sum, path):\n",
    "        if len(tree[node]) < 2: # leave node\n",
    "            cur_sum += tree[node][0]\n",
    "            path.append(cur_sum)\n",
    "            return \n",
    "\n",
    "        cur_sum += tree[node][0] # add current node value to the sum value\n",
    "        self.dfs(tree[node][1], tree, cur_sum, path)\n",
    "        if len(tree[node]) > 2:\n",
    "            self.dfs(tree[node][2], tree, cur_sum, path)\n",
    "        return\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(lambda: defaultdict(int))\n",
    "\n",
    "        for num in nums:\n",
    "            dep = num // 100\n",
    "            pos = (num//10) % 10\n",
    "            val = num % 10\n",
    "            d[dep][pos] = val\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        def dfs(dep, pos, cur):\n",
    "            if dep not in d or pos not in d[dep]:\n",
    "                return 0\n",
    "\n",
    "            cur += d[dep][pos]\n",
    "\n",
    "            left = dfs(dep+1, 2*pos-1, cur)\n",
    "\n",
    "            right = dfs(dep+1, 2*pos, cur)\n",
    "\n",
    "            if left == 0 and right == 0:\n",
    "                nonlocal ret\n",
    "                ret += cur\n",
    "                return\n",
    "\n",
    "        dfs(1, 1, 0)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        # print(1//2) # 0\n",
    "        rootToPath = dict() # 从key到root的path sum, root为1\n",
    "        rootToPath[0] = 0\n",
    "        for num in nums:\n",
    "            depth = num // 100\n",
    "            pos = num // 10 % 10\n",
    "            val = num % 10\n",
    "            idx = 2**(depth - 1) + pos - 1\n",
    "            rootToPath[idx] = rootToPath[idx//2] + val\n",
    "        res = 0\n",
    "        for path, val in rootToPath.items():\n",
    "            if not path * 2 in rootToPath and not path * 2 + 1 in rootToPath:\n",
    "            # if leaf node\n",
    "                res += val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 记录从根节点到当前节点的路径和【设：根节点索引从1开始】\n",
    "        dic = dict()\n",
    "        dic[0] = 0 # 初始化\n",
    "\n",
    "        # 自己画个图，就知道当前节点k的左节点索引为2*k，右节点索引为2*k+1\n",
    "        # 所以当前索引为k的话，那其父母索引为k//2\n",
    "        for n in nums:\n",
    "            # idx = 2*(depth-1) + (pos-1)\n",
    "            idx = 2**(n//100-1) + ((n//10)%10-1)\n",
    "            dic[idx] = dic[idx//2] + n%10\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        for k in dic:\n",
    "            left_idx = 2*k\n",
    "            right_idx = 2*k+1\n",
    "\n",
    "            # 如果为叶子节点\n",
    "            if left_idx not in dic and right_idx not in dic:\n",
    "\n",
    "                res += dic[k]\n",
    "        \n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(lambda: defaultdict(int))\n",
    "\n",
    "        for num in nums:\n",
    "            dep = num // 100\n",
    "            pos = (num//10) % 10\n",
    "            val = num % 10\n",
    "            d[dep][pos] = val\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        def dfs(dep, pos, cur):\n",
    "            if dep not in d or pos not in d[dep]:\n",
    "                return -1\n",
    "\n",
    "            cur += d[dep][pos]\n",
    "\n",
    "            left = dfs(dep+1, 2*pos-1, cur)\n",
    "\n",
    "            right = dfs(dep+1, 2*pos, cur)\n",
    "\n",
    "            if left == -1 and right == -1:\n",
    "                nonlocal ret\n",
    "                ret += cur\n",
    "                # print\n",
    "                return\n",
    "\n",
    "        dfs(1, 1, 0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 记录从根节点到当前节点的路径和【设：根节点索引从1开始】\n",
    "        dic = dict()\n",
    "        dic[0] = 0 # 初始化\n",
    "\n",
    "        # 自己画个图，就知道当前节点k的左节点索引为2*k，右节点索引为2*k+1\n",
    "        # 所以当前索引为k的话，那其父母索引为k//2\n",
    "        for n in nums:\n",
    "            idx = 2**(n//100-1) + ((n//10)%10-1)\n",
    "            dic[idx] = dic[idx//2] + n%10\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        for k in dic:\n",
    "            left_idx = 2*k\n",
    "            right_idx = 2*k+1\n",
    "\n",
    "            # 如果为叶子节点\n",
    "            if left_idx not in dic and right_idx not in dic:\n",
    "\n",
    "                res += dic[k]\n",
    "        \n",
    "        return res\n",
    "            \n",
    "#  2^n-1\n",
    "# [1]\n",
    "\n",
    "#    i\n",
    "#  0 1 2  father-> (i-1)//2\n",
    "# [1,2,3]  \n",
    "# left: 2*i+1\n",
    "# right:2*i+2\n",
    "\n",
    "# idx = 1\n",
    "# 2,1\n",
    "# [1] - 2**n-1\n",
    "\n",
    "\n",
    "\n",
    "#                 113      1 - 1                              1\n",
    "#                 /  \\                                        /\\\n",
    "#             215     221  2 - 2**2-1 = 3       2-1+1-1 = 2      2-1+2-1 = 3    \n",
    "#             /\\       /\\\n",
    "#                          3 - 1+2+4=7 = 2**3-1\n",
    "\n",
    "# [0(3), 1(5), 2(1)]\n",
    "\n",
    "# h = num//100           idx = 2**(h-1) - 1 + d    2-1+2-1 = 2\n",
    "# d = (num//10)%10\n",
    "# o = num%10\n",
    "\n",
    "# i: father -> (i-1)//2\n",
    "# left: 2*i+1\n",
    "# right:2*i+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        l = [-1] * 15\n",
    "        for n in nums:\n",
    "            d = n // 100\n",
    "            p = (n // 10) % 10\n",
    "            v = n % 10\n",
    "            i = 2 ** (d - 1) - 1 + p - 1\n",
    "            #print(f'{n} {d} {p} {v} {i}')\n",
    "            l[i] = v\n",
    "\n",
    "        self.ret = 0\n",
    "        def dfs(i, s, l):\n",
    "            s += l[i]\n",
    "            lc = 2 * i + 1\n",
    "            rc = 2 * i + 2\n",
    "            bl = lc < 15 and l[lc] > -1\n",
    "            br = rc < 15 and l[rc] > -1\n",
    "            if not bl and not br:\n",
    "                self.ret += s\n",
    "                return\n",
    "            if bl:\n",
    "                dfs(lc, s, l)\n",
    "            if br:\n",
    "                dfs(rc, s, l)\n",
    "        dfs(0, 0, l)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,v):\n",
    "        self.v=v\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        hashmap={}\n",
    "        for num in nums[1:]:\n",
    "            x,y,z=num//100,num//10%10,num%10\n",
    "            seq=pow(2,x-1)+y-1\n",
    "            hashmap[seq]=Node(z)\n",
    "        hashmap[1]=Node(nums[0]%10)\n",
    "        ans=0\n",
    "        def dfs(seq,sum):\n",
    "            nonlocal ans\n",
    "            if seq*2 not in hashmap and seq*2+1 not in hashmap:\n",
    "                sum+=hashmap[seq].v\n",
    "                ans+=sum\n",
    "                return\n",
    "            if seq*2 in hashmap:\n",
    "                dfs(seq*2,sum+hashmap[seq].v)\n",
    "            if seq*2+1 in hashmap:\n",
    "                dfs(seq*2+1,sum+hashmap[seq].v)\n",
    "        dfs(1,0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        root = Node(nums[0] % 10)\n",
    "        for x in nums[1:]:\n",
    "            depth, pos, val = x // 100, x // 10 % 10, x % 10\n",
    "            pos -= 1\n",
    "            curr = root\n",
    "            for d in range(depth - 2, -1, -1):\n",
    "                if pos < 2 ** d:\n",
    "                    curr.left = curr = curr.left or Node(val)\n",
    "                else:\n",
    "                    curr.right = curr = curr.right or Node(val)\n",
    "                pos %= 2 ** d\n",
    "        \n",
    "        def dfs(node, running_sum):\n",
    "            if not node:\n",
    "                return\n",
    "            running_sum += node.val\n",
    "            if not node.left and not node.right:\n",
    "                self.ans += running_sum\n",
    "            else:\n",
    "                dfs(node.left, running_sum)\n",
    "                dfs(node.right, running_sum)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        que = Counter()\n",
    "        for i in nums:\n",
    "            layer, idx, val = map(int, str(i))\n",
    "            que[2 ** (layer - 1) + idx - 1] = val \n",
    "        \n",
    "        def dfs(node, x):\n",
    "            nonlocal ans \n",
    "            if 2 * node in que:\n",
    "                dfs(2 * node, x + que[2 * node])\n",
    "            if 2 * node + 1 in que:\n",
    "                dfs(2 * node + 1, x + que[2 * node + 1])\n",
    "            if 2 * node not in que and 2 * node + 1 not in que:\n",
    "                ans += x \n",
    "        \n",
    "        dfs(1, que[1])\n",
    "        return ans \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.node_map = {}\n",
    "\n",
    "        for num in nums:\n",
    "            val = num % 10\n",
    "            code = num // 10\n",
    "\n",
    "            self.node_map[code] = val \n",
    "\n",
    "        root = nums[0] // 10\n",
    "\n",
    "        self.res = 0\n",
    "\n",
    "        self.traverse(root, 0)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, path):\n",
    "        if root not in self.node_map:\n",
    "            return \n",
    "\n",
    "        path += self.node_map[root]\n",
    "\n",
    "        root_row, root_col = self.decode(root)\n",
    "        left = (root_row + 1) * 10 + (2 * root_col - 1)\n",
    "        right = (root_row + 1) * 10 + (2 * root_col)\n",
    "\n",
    "        if left not in self.node_map and right not in self.node_map:\n",
    "            self.res += path \n",
    "            return \n",
    "\n",
    "        self.traverse(left, path)\n",
    "        self.traverse(right, path)\n",
    "\n",
    "    def decode(self, code):\n",
    "        row = code // 10\n",
    "        col = code % 10\n",
    "        return row, col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        values = {x // 10: x % 10 for x in nums}\n",
    "\n",
    "        def dfs(node, total): # node是每个num的前两位数\n",
    "            if node not in values: return\n",
    "            total += values[node]\n",
    "            depth, pos = node // 10, node % 10\n",
    "            left = (depth + 1) * 10 + 2 * pos - 1\n",
    "            right = left + 1\n",
    "\n",
    "            # 如果node是叶子节点，更新self.res\n",
    "            if left not in values and right not in values:\n",
    "                self.res += total\n",
    "            else:\n",
    "                dfs(left, total)\n",
    "                dfs(right, total)\n",
    "\n",
    "        dfs(nums[0]//10, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        m = defaultdict(lambda: defaultdict(int))\n",
    "        mx = 0\n",
    "        for i, c in enumerate(nums):\n",
    "            depth = c // 100\n",
    "            mx = max(mx, depth)\n",
    "            c %= 100\n",
    "            pos = c // 10\n",
    "            val = c % 10\n",
    "            m[depth][pos] = val\n",
    "        ans = 0\n",
    "        # 叶子节点 不一定是深度最深的节点\n",
    "        depth_set = list(m.keys())\n",
    "        for depth in depth_set:\n",
    "            for pos in m[depth]:\n",
    "                if (2 * pos - 1) not in m[depth+1] and (2 * pos) not in m[depth+1]:\n",
    "                    cur = 0\n",
    "                    cur_layer = depth\n",
    "                    while cur_layer:\n",
    "                        cur += m[cur_layer][pos]\n",
    "                        pos = (pos + 1) >> 1\n",
    "                        cur_layer -= 1\n",
    "                    ans += cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.nodes = {}\n",
    "\n",
    "        for ele in nums:\n",
    "            code = ele // 10\n",
    "            val = ele % 10\n",
    "            self.nodes[code] = val\n",
    "\n",
    "        root = nums[0] // 10\n",
    "\n",
    "        self.res = 0\n",
    "        self.traverse(root, 0)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, path_sum):\n",
    "        if root not in self.nodes:\n",
    "            return \n",
    "\n",
    "        row, col = self.decode(root)\n",
    "\n",
    "        left = (row + 1) * 10 + (col * 2 - 1)\n",
    "        right = (row + 1) * 10 + (col * 2)\n",
    "\n",
    "        path_sum += self.nodes[root]\n",
    "\n",
    "        if left not in self.nodes and right not in self.nodes:\n",
    "            self.res += path_sum\n",
    "            return\n",
    "\n",
    "        self.traverse(left, path_sum)\n",
    "        self.traverse(right, path_sum)\n",
    "\n",
    "    def decode(self, code):\n",
    "        row = code // 10\n",
    "        col = code % 10\n",
    "\n",
    "        return row, col\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = {(n // 100, n // 10 % 10): n % 10 for n in nums}\n",
    "\n",
    "        def dfs(node, currSum):\n",
    "\n",
    "            if not node in tree:\n",
    "                return 0\n",
    "            \n",
    "            currSum += tree[node]\n",
    "\n",
    "            layer, pos = node\n",
    "            left = (layer + 1, pos * 2 - 1)\n",
    "            right = (layer + 1, pos * 2)\n",
    "\n",
    "            if not left in tree and not right in tree:\n",
    "                return currSum\n",
    "            \n",
    "            return dfs(left, currSum) + dfs(right, currSum)\n",
    "        \n",
    "        return dfs((1, 1), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        \n",
    "        layers = []\n",
    "        \n",
    "        for i in range(1,5):\n",
    "            layers.append([-1 for _ in range(2**(i-1))])\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            cur = nums[i]\n",
    "            x = cur // 100\n",
    "            y = (cur // 10) % 10\n",
    "            v = cur % 10\n",
    "            layers[x-1][y-1] = v\n",
    "        \n",
    "        root = TreeNode(layers[0][0])\n",
    "        layers[0][0] = root\n",
    "\n",
    "        for i in range(len(layers)-1):\n",
    "            for j in range(len(layers[i])):\n",
    "                cur = layers[i][j]\n",
    "                if cur == -1:\n",
    "                    continue\n",
    "                \n",
    "                if layers[i+1][j*2] != -1:\n",
    "                    l = TreeNode(layers[i+1][j*2])\n",
    "                    cur.left = l\n",
    "                    layers[i+1][j*2] = l\n",
    "                \n",
    "                if layers[i+1][j*2+1] != -1:\n",
    "                    r = TreeNode(layers[i+1][j*2+1])\n",
    "                    cur.right = r\n",
    "                    layers[i+1][j*2+1] = r\n",
    "        for x in layers:\n",
    "            print(x)\n",
    "\n",
    "        def dfs(node, cur):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            if not node.left and not node.right:\n",
    "                return node.val + cur\n",
    "            \n",
    "            l = dfs(node.left, cur + node.val)\n",
    "            r = dfs(node.right, cur + node.val)\n",
    "\n",
    "            return l + r\n",
    "\n",
    "        return dfs(root, 0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tol = 1<<5\n",
    "        l = [-1]*tol\n",
    "        for num in nums:\n",
    "            d = num // 100\n",
    "            p = (num%100)//10\n",
    "            v = num%10\n",
    "            id = (1<<(d-1)) - 1 + (p-1)\n",
    "            l[id]=v\n",
    "        ans = 0\n",
    "        # print(l)\n",
    "        for i in range(16):\n",
    "            if l[i]==-1:\n",
    "                continue\n",
    "            if l[2*i+1]==-1 and l[2*i+2]==-1:\n",
    "                ans+=l[i]\n",
    "            else:\n",
    "                if l[2*i+2]!=-1:\n",
    "                    l[2*i+2]+=l[i]\n",
    "                if l[2*i+1]!=-1:\n",
    "                    l[2*i+1]+=l[i]\n",
    "            # print(l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        def dfs(d, p, curr_sum):\n",
    "            if (d, p) not in nodes:\n",
    "                return  0\n",
    "\n",
    "            curr_sum += nodes[(d, p)]\n",
    "            if (d + 1, 2 * p - 1) not in nodes and (d + 1, 2 * p) not in nodes:\n",
    "                return curr_sum\n",
    "            return dfs(d + 1, 2 * p - 1, curr_sum) + dfs(d + 1, 2 * p, curr_sum)\n",
    "        \n",
    "        nodes = {}\n",
    "        for num in nums:\n",
    "            d, p, v = num // 100, num // 10 % 10, num % 10\n",
    "            nodes[(d, p)] = v\n",
    "        \n",
    "        return dfs(1, 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        values = {x // 10: x % 10 for x in nums}\n",
    "        def dfs(node, running_sum = 0):\n",
    "            if node not in values: return\n",
    "            running_sum += values[node]\n",
    "            depth, pos = divmod(node, 10)\n",
    "            left = (depth + 1) * 10 + 2 * pos - 1\n",
    "            right = left + 1\n",
    "\n",
    "            if left not in values and right not in values:\n",
    "                self.ans += running_sum\n",
    "            else:\n",
    "                dfs(left, running_sum)\n",
    "                dfs(right, running_sum)\n",
    "\n",
    "        dfs(nums[0] // 10)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        dic[0] = 0\n",
    "        for num in nums:\n",
    "            h = num // 100          #\n",
    "            d = (num // 10) % 10    #\n",
    "            idx = 2**(h-1) + d - 1  #  11 -> 1, 21 -> 2\n",
    "            dic[idx] = dic[idx//2] + num%10\n",
    "        res = 0\n",
    "        for i in dic.keys():\n",
    "            left = 2*(i-1) + 1 + 1\n",
    "            right = 2*(i-1) + 2 + 1\n",
    "            if left not in dic and right not in dic:\n",
    "                res += dic[i]\n",
    "        return res\n",
    "\n",
    "\n",
    "#  2^n-1\n",
    "# [1]\n",
    "\n",
    "#    i\n",
    "#  0 1 2  father-> (i-1)//2\n",
    "# [1,2,3]  \n",
    "# left: 2*i+1\n",
    "# right:2*i+2\n",
    "\n",
    "# idx = 1\n",
    "# 2,1\n",
    "# [1] - 2**n-1\n",
    "\n",
    "\n",
    "\n",
    "#                 113      1 - 1                              1\n",
    "#                 /  \\                                        /\\\n",
    "#             215     221  2 - 2**2-1 = 3       2-1+1-1 = 2      2-1+2-1 = 3    \n",
    "#             /\\       /\\\n",
    "#                          3 - 1+2+4=7 = 2**3-1\n",
    "\n",
    "# [0(3), 1(5), 2(1)]\n",
    "\n",
    "# h = num//100           idx = 2**(h-1) - 1 + d    2-1+2-1 = 2\n",
    "# d = (num//10)%10\n",
    "# o = num%10\n",
    "\n",
    "# i: father -> (i-1)//2\n",
    "# left: 2*i+1\n",
    "# right:2*i+2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = {}\n",
    "        \n",
    "        for num in nums:\n",
    "            depth = num // 100\n",
    "            pos = num // 10 % 10\n",
    "            val = num % 10\n",
    "\n",
    "            k = 2 ** (depth - 1) + pos - 1\n",
    "            tree[k] = val\n",
    "        # print(tree)\n",
    "        res = 0\n",
    "        def dfs(path, i):\n",
    "            if i not in tree:\n",
    "                return\n",
    "            path += tree[i]\n",
    "            if i * 2 not in tree and i * 2 + 1 not in tree:\n",
    "                nonlocal res\n",
    "                res += path\n",
    "\n",
    "            if i * 2 in tree:\n",
    "                dfs(path, i * 2)\n",
    "\n",
    "            if i * 2 + 1 in tree:\n",
    "                dfs(path, i * 2 + 1)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        dfs(0,1)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.pathsum = 0\n",
    "        n = len(nums)\n",
    "        node_dict = {}\n",
    "        maxLayer = 1\n",
    "        for i in range(n):\n",
    "            layer = nums[i] // 100\n",
    "            maxLayer = max(maxLayer, layer)\n",
    "            index = (nums[i] - layer * 100) // 10\n",
    "            value = nums[i] - layer * 100 - index * 10\n",
    "            node_dict[(layer, index)] = [value, i]\n",
    "        \n",
    "        def dfs(begin, path_sum):\n",
    "            if not begin < n:\n",
    "                return\n",
    "            # path_sum = 0\n",
    "            layer = nums[begin] // 100\n",
    "            index =(nums[begin] - layer * 100) // 10\n",
    "            value = node_dict[(layer,index)][0]\n",
    "            path_sum += value\n",
    "            \n",
    "            left_index = index * 2 - 1\n",
    "            right_index = index * 2\n",
    "            if (layer+1, left_index) in node_dict:\n",
    "                dfs(node_dict[(layer+1, left_index)][1], path_sum)\n",
    "            if (layer+1, right_index) in node_dict:\n",
    "                dfs(node_dict[(layer+1, right_index)][1], path_sum)\n",
    "            if (layer+1, left_index) not in node_dict and (layer+1, right_index) not in node_dict:\n",
    "                self.pathsum += path_sum\n",
    "            \n",
    "        dfs(0, 0)\n",
    "        return self.pathsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        tree = {}\n",
    "        \n",
    "        for v in nums:\n",
    "            depthPos = v // 10\n",
    "            val = v % 10\n",
    "            tree[depthPos] = val\n",
    "        @cache\n",
    "        def dfs(depthPos,curSum):\n",
    "            if depthPos not in tree:\n",
    "                return 0\n",
    "\n",
    "            depth = depthPos // 10 + 1\n",
    "            pos = 2 * (depthPos % 10) - 1\n",
    "\n",
    "            leftDP = depth * 10 + pos\n",
    "            rightDP = leftDP + 1\n",
    "\n",
    "            if leftDP not in tree and rightDP not in tree:\n",
    "                return tree[depthPos] + curSum\n",
    "\n",
    "            l = dfs(leftDP,curSum + tree[depthPos])\n",
    "            r = dfs(rightDP,curSum + tree[depthPos])\n",
    "\n",
    "            return l + r\n",
    "        \n",
    "        return dfs(11,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val: int, left: TreeNode = None, right: TreeNode = None) -> TreeNode:\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        dic = dict()\n",
    "\n",
    "        for num in nums[::-1]:\n",
    "            d = num // 100\n",
    "            p = (num // 10) % 10 - 1\n",
    "            v = num % 10\n",
    "\n",
    "            node = TreeNode(v)\n",
    "            lc = (d+1, p*2)\n",
    "            rc = (d+1, p*2+1)\n",
    "\n",
    "            if lc in dic:\n",
    "                node.left = dic[lc]\n",
    "            if rc in dic:\n",
    "                node.right = dic[rc]\n",
    "            \n",
    "            dic[(d, p)] = node\n",
    "        \n",
    "        res = 0\n",
    "        def pSum(root: TreeNode, preSum: int) -> None:\n",
    "            nonlocal res\n",
    "\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            preSum += root.val\n",
    "            if not root.left and not root.right:\n",
    "                res += preSum\n",
    "                return\n",
    "            \n",
    "            pSum(root.left, preSum)\n",
    "            pSum(root.right, preSum)\n",
    "        \n",
    "        pSum(dic[(1,0)], 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        d = {x // 10 : x % 10 for x in nums}\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x,s):\n",
    "            if x in d:\n",
    "                nonlocal ans\n",
    "                s += d[x]\n",
    "                depth,pos = x // 10,x % 10\n",
    "                left = (depth + 1) * 10 + 2*pos - 1\n",
    "                if left not in d and left + 1 not in d:\n",
    "                    ans += s\n",
    "                else:\n",
    "                    dfs(left,s)\n",
    "                    dfs(left + 1,s)\n",
    "        \n",
    "        dfs(nums[0] // 10,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        nodes = {}\n",
    "        for num in nums:\n",
    "            level = num // 100\n",
    "            num %= 100\n",
    "            col = num // 10\n",
    "            num %= 10\n",
    "            val = num\n",
    "            nodes[(level, col)] = val\n",
    "        \n",
    "        totalSum = 0\n",
    "        def _DFS(level, col, curSum):\n",
    "            nonlocal totalSum\n",
    "            # left child\n",
    "            curSum += nodes[(level, col)]\n",
    "            if (level + 1, col * 2 - 1) in nodes or (level + 1, col * 2) in nodes:\n",
    "                if (level + 1, col * 2 - 1) in nodes:\n",
    "                    _DFS(level + 1, col * 2 - 1, curSum)\n",
    "                if (level + 1, col * 2) in nodes:\n",
    "                    _DFS(level + 1, col * 2, curSum)\n",
    "            else:\n",
    "                totalSum += curSum\n",
    "        \n",
    "        _DFS(1, 1, 0)\n",
    "        \n",
    "        return totalSum\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        # nums: 前序遍历\n",
    "        # convert nums to string of nums\n",
    "        nums_str = [str(x) for x in nums]\n",
    "        prefix_to_num = dict()\n",
    "        for x in nums_str:\n",
    "            prefix_to_num[x[:2]] = x\n",
    "\n",
    "        def code2info(num) -> List[int]:\n",
    "            res = [int(c) for c in num]\n",
    "            return res\n",
    "\n",
    "        all_sum = 0\n",
    "        # queue: (curr_node, curr_path_sum(included curr_node's val))\n",
    "        queue = [(nums_str[0], int(nums_str[0][2]))]\n",
    "        while queue:\n",
    "            curr_node, curr_sum = queue.pop(0)\n",
    "            curr_info = code2info(curr_node)\n",
    "            left_prefix = str(curr_info[0]+1) + str(2*curr_info[1]-1)\n",
    "            right_prefix = str(curr_info[0]+1) + str(2*curr_info[1])\n",
    "\n",
    "            # if curr_node is leaf nonde\n",
    "            if left_prefix not in prefix_to_num and right_prefix not in prefix_to_num:\n",
    "                all_sum += curr_sum\n",
    "                continue\n",
    "            \n",
    "            # if has left child\n",
    "            if left_prefix in prefix_to_num:\n",
    "                left_child = prefix_to_num[left_prefix]\n",
    "                queue.append((left_child, curr_sum + int(left_child[2])))\n",
    "            \n",
    "            # if has right child\n",
    "            if right_prefix in prefix_to_num:\n",
    "                right_child = prefix_to_num[right_prefix]\n",
    "                queue.append((right_child, curr_sum + int(right_child[2])))\n",
    "        \n",
    "        return all_sum\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val: int):\n",
    "        self.val = val\n",
    "        self.left = self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        root = Node(nums[0] % 10)\n",
    "\n",
    "        for x in nums[1:]:\n",
    "            depth, pos, val = x//100, x//10 % 10, x % 10\n",
    "            pos -= 1\n",
    "            cur = root\n",
    "            for d in range(depth - 2, -1, -1):\n",
    "                if pos < 2**d:\n",
    "                    cur.left = cur = cur.left or Node(val)\n",
    "                else:\n",
    "                    cur.right = cur = cur.right or Node(val)\n",
    "\n",
    "                pos %= 2**d\n",
    "\n",
    "        def dfs(node, running_sum = 0):\n",
    "            if not node: return\n",
    "            running_sum += node.val\n",
    "            if not node.left and not node.right:\n",
    "                self.ans += running_sum\n",
    "            else:\n",
    "                dfs(node.left, running_sum)\n",
    "                dfs(node.right, running_sum)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        self.pathsum = 0\n",
    "        n = len(nums)\n",
    "        node_dict = {}\n",
    "        maxLayer = 1\n",
    "        for i in range(n):\n",
    "            layer = nums[i] // 100\n",
    "            maxLayer = max(maxLayer, layer)\n",
    "            index = (nums[i] - layer * 100) // 10\n",
    "            value = nums[i] - layer * 100 - index * 10\n",
    "            node_dict[(layer, index)] = [value, i]\n",
    "        \n",
    "        def dfs(begin, path_sum):\n",
    "            if not begin < n:\n",
    "                return\n",
    "            # path_sum = 0\n",
    "            layer = nums[begin] // 100\n",
    "            index =(nums[begin] - layer * 100) // 10\n",
    "            value = node_dict[(layer,index)][0]\n",
    "            path_sum += value\n",
    "            \n",
    "            left_index = index * 2 - 1\n",
    "            right_index = index * 2\n",
    "            if (layer+1, left_index) in node_dict:\n",
    "                dfs(node_dict[(layer+1, left_index)][1], path_sum)\n",
    "            if (layer+1, right_index) in node_dict:\n",
    "                dfs(node_dict[(layer+1, right_index)][1], path_sum)\n",
    "            if (layer+1, left_index) not in node_dict and (layer+1, right_index) not in node_dict:\n",
    "                self.pathsum += path_sum\n",
    "            \n",
    "        dfs(0, 0)\n",
    "        return self.pathsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pathSum(self, nums):\n",
    "        self.ans = 0\n",
    "        values = {x // 10: x % 10 for x in nums}\n",
    "        print(values)\n",
    "        def dfs(node, running_sum = 0):\n",
    "            if node not in values: return\n",
    "            running_sum += values[node]\n",
    "            depth, pos = divmod(node, 10)\n",
    "            left = (depth + 1) * 10 + 2 * pos - 1\n",
    "            right = left + 1\n",
    "\n",
    "            if left not in values and right not in values:\n",
    "                self.ans += running_sum\n",
    "            else:\n",
    "                dfs(left, running_sum)\n",
    "                dfs(right, running_sum)\n",
    "\n",
    "        dfs(nums[0] // 10)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        pos2val = {}\n",
    "        for ii in nums:\n",
    "            ii = str(ii)\n",
    "            pos = ii[:2]\n",
    "            val = ii[2]\n",
    "            pos2val[pos] = val\n",
    "\n",
    "        self.ans = 0\n",
    "        def dfs(n, current_sum):\n",
    "            n = [int(x) for x in n]\n",
    "            level, idx, val = n\n",
    "\n",
    "            current_sum += val\n",
    "            left_idx = idx * 2 - 1\n",
    "            right_idx = idx * 2\n",
    "            left_pos = f'{level + 1}{left_idx}'\n",
    "            right_pos = f'{level + 1}{right_idx}'\n",
    "            if left_pos not in pos2val and right_pos not in pos2val:\n",
    "                self.ans += current_sum\n",
    "                return\n",
    "            \n",
    "            if left_pos in pos2val:\n",
    "                dfs(left_pos + pos2val[left_pos], current_sum)\n",
    "            if right_pos in pos2val:\n",
    "                dfs(right_pos + pos2val[right_pos], current_sum)\n",
    "\n",
    "        dfs(str(nums[0]), 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        def dfs(depth, pos, cur_sum):\n",
    "            # 10x + y -> 10(x+1) + 2y-1, 10(x+1) + 2y\n",
    "            nonlocal res\n",
    "            l, r = 10 * (depth + 1) + 2 * pos - 1, 10 * (depth + 1) + 2 * pos\n",
    "            if l not in memo and r not in memo:  # leaf\n",
    "                res += cur_sum\n",
    "                return\n",
    "            if l in memo:\n",
    "                dfs(depth + 1, pos * 2 - 1, cur_sum + memo[l])\n",
    "            if r in memo:\n",
    "                dfs(depth + 1, pos * 2, cur_sum + memo[r])\n",
    "\n",
    "        memo = {}  # depth+pos: val\n",
    "        for num in nums:\n",
    "            memo[num // 10] = num % 10\n",
    "        res = 0\n",
    "        dfs(1, 1, memo[11])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "        pos2val = {}\n",
    "        for ii in nums:\n",
    "            pos2val[ii // 10] = ii % 10\n",
    "        \n",
    "        self.ans = 0\n",
    "        def dfs_sum(pos, current_sum):\n",
    "            if pos not in pos2val:\n",
    "                return 0\n",
    "            \n",
    "            val = pos2val[pos]\n",
    "            current_sum += val\n",
    "            \n",
    "            level = pos // 10\n",
    "            idx = pos % 10\n",
    "            left_pos = (level + 1) * 10 + idx * 2 - 1\n",
    "            right_pos = (level + 1) * 10 + idx * 2\n",
    "            if left_pos not in pos2val and right_pos not in pos2val:\n",
    "                self.ans += current_sum\n",
    "            dfs_sum(left_pos, current_sum)\n",
    "            right = dfs_sum(right_pos, current_sum)\n",
    "        \n",
    "        dfs_sum(nums[0] // 10, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, nums: List[int]) -> int:\n",
    "\n",
    "        tree = {(n // 100, n // 10 % 10): n % 10 for n in nums}\n",
    "\n",
    "        def dfs(currNode, currSum):\n",
    "\n",
    "            if not currNode in tree:\n",
    "                return 0\n",
    "\n",
    "            currSum += tree[currNode]\n",
    "            layer, pos = currNode\n",
    "            leftNode = (layer + 1, 2 * pos - 1)\n",
    "            rightNode = (layer + 1, 2 * pos)\n",
    "\n",
    "            if not leftNode in tree and not rightNode in tree:\n",
    "                return currSum\n",
    "\n",
    "            return dfs(leftNode, currSum) + dfs(rightNode, currSum)\n",
    "\n",
    "        # s = dfs((0, 0), )\n",
    "\n",
    "        return dfs((1, 1), 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
